Today, the protection of personal information and confidential information has been becoming more and more important, and the market of services that use personal information or confidential information has been expanding. Examples of such services include a service that utilizes position information of an individual user that can be obtained from a smart phone, etc. This has generated attention for information concealing techniques, which enable the utilization of personal information/confidential information while keeping such information in a protected state. Examples of information concealing techniques include a technique that uses a cryptography technique or a statistics technique in accordance with data type or service requirements.
As a concealing technique that uses cryptography, a homomorphic encryption technique is known. A homomorphic encryption technique is one public key encryption method that uses a pair of different keys for encryption and decryption, and has a function of permitting data manipulation while keeping the data in an encrypted state.
By using a homomorphic encryption method, when addition or multiplication is performed on an encrypted text, it is possible to obtain an encrypted text, which is a computation result after performing addition or multiplication, without decrypting an encrypted text. This feature of a homomorphic encryption method is considered to be utilized in the field of electronic voting/electronic cash and recently in the cloud computing field. As homomorphic encryption methods related to addition or multiplication, an RSA encryption method, which only permits multiplication, and an Additive ElGamal encryption, which only permits addition, are known. In a multiplication homomorphic encryption method, when encrypted texts of plain texts (messages) a and b are E(a) and E(b), encrypted text E(a·b) of the product of plain texts a·b can be calculated from E(a) and E(b). Also, in an addition homomorphic encryption method, when encrypted texts of plain texts a and b are E(a) and E(b), the encrypted text E(a+b) of the sum of the plain texts a+b can be calculated from E(a) and E(b). By using a homomorphic encryption method to perform addition or multiplication on encrypted texts, it is possible to obtain an encrypted text as a computation result of performing addition or multiplication without decrypting an encrypted text. This feature of a homomorphic encryption method is expected to be utilized in the field of electronic voting/electronic cash and recently in the cloud computing field.
In recent years, as an encryption method having homomorphy for both addition and multiplication, a fully homomorphic encryption method is known. When addition and multiplication are possible while keeping targets in an encrypted state, operations such as exclusive OR, AND, and NOT are possible while keeping targets in an encrypted state. In other words, a fully homomorphic encryption method has homomorphy for all operations performed by logical circuits. Although, at first, only a theoretical implementation method was introduced and practical configurations were not made public, examples of specific configurations of generating a key and a cryptography method that expanded types of data that can be encrypted have also been proposed. In these examples of specific configurations of generating a key, keys such as a public key and a secret key are in the form of matrix.
A homomorphic encryption method can be used in a system that checks the similarity between two pieces of information.
Patent Document 1: Japanese Laid-open Patent Publication No. 2011-145512
Non-Patent Document 1: C. Gentry, “Fully Homomorphic encryption using ideal lattices”, STOC 2009, pp. 169-178, 2009
Non-Patent Document 2: C. Gentry and S. Halevi, “Implementing Gentry's Fully Homomorphic Encryption Scheme”, EUROCRYPT 2011, LNCS 6632, pp. 129-148, 2011
Non-Patent Document 3: Yasuda, Yajima, Shimoyama, and Kogure, “Secret totalization of purchase histories of companies in cloud” SCIS 2012